package 我的Java学习_算法基础.day_08;

import java.util.Arrays;
import java.util.Scanner;

import static java.lang.Math.min;

/**
 * @author 挚爱之夕
 * @date 2021/8/23 - 08 - 23 - 9:27
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _123_快速渡河问题 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[] speed = new int[n];
            for (int j = 0; j < n; j++) {
                speed[j] = sc.nextInt();
            }
            Arrays.sort(speed);
            f(n,speed);
        }
    }
    private static void f(int n,int[] speed){
        int left = n;
        int ans = 0;
        while(left>0){
            if(left==1){//只有1人
                ans+=speed[0];
                break;
            }else if(left==2){//有两人
                ans+=speed[1];
                break;
            }else if(left==3){//有三人
                ans+=speed[2]+speed[0]+speed[1];
                break;
            }else{//4人大于4人情况：将最慢两人运过去
                //1,2出发,1返回,最后两名出发，2返回
                int s1 = speed[1] +speed[0] +speed[left-1]+speed[1];
                //1,n出发，1返回，1，n-1出发，1返回
                int s2 = speed[left-1] +speed[0]+speed[left-2] + speed[0];
                ans+=min(s1,s2);
                left-=2;
            }

        }
        System.out.println(ans);
    }
}
